package chapter1;

import java.util.Arrays;

/**
 * create by yongli on 2021-07-09 09:33
 * keep/stay enthusiastic
 * 目前算法均考虑有效输入的情况
 */

public class Section4 {

    public static void main(String[] args) {
        int[] a = {13, 0, 3232, 23, 3, 10, 121, 2113, 235};
        System.out.println(sum2count(13, a));
    }

    // 排序的复杂度为NlogN,二分查找为logN,整个运行复杂度为NlogN
    // 所以排序软件决定了大部分软件的性能
    // 简单的话
    public static int sum2count(int sum, int[] a) {
        Arrays.sort(a);
        int count = 0;
        for (int i = 0; i < a.length; i++) {
            int b = sum - a[i];
            // 在其后搜索
            int idx = rank(b, a);
//            if(idx!=-1){
//                count++;
//            }
            // 这个就很灵性了
            if (rank(b, a) > i) {
                count++;
            }
        }
        return count;
    }

    public static int rank(int target, int[] a) {
        int low = 0, high = a.length - 1;

        while (low <= high) {
            int mid = (low + high) / 2;
            if (a[mid] == target) {
                return mid;
            }
            if (a[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

}
